Spatial reasoning is commonly known as reasoning about shape, measurement, depiction and navigation. Shape relates to the structure of space. Measurement relates to the dimension of space. Depiction relates to the representation of space entities. Navigation relates to large-scale space and concepts such as position, direction, distance, and routes. Spatial reasoning creates representation and applies rules that could describe the relations or changes in the relations of shape, measurement, depiction and navigation.
Humans develop spatial reasoning capability by first developing spatial representation then integrating multiple representations by their associated relations and rules. Similarly, spatial reasoning by computer involves the development of models for representation of spatial entities and the inference of information about spatial relations within the model framework. Spatial knowledge could be stored in a human cognitive map like representation such as the Spatial Semantic Hierarchy (B. Kuipers. 2000. The Spatial Semantic Hierarchy. Artificial Intelligence 119: 191-233.) The prevailing goal of a computerized spatial reasoning method is to discover meaningful cues and premises from the spatial relations of multiple sets of objects residing in multidimensional space.
There are many practical applications for spatial reasoning. For example, spatial reasoning is critical to the Geographical Information Systems (GIS). GIS is a computer system capable of assembling, storing, manipulating, and displaying geographically referenced information, i.e. data identified according to its location. It can be used for scientific investigations, resource management, and development planning. (Geographical Information Systems http://www.usgs.gov/research/gis/title.html)
In a cell image informatics application, spatial reasoning relates the target segmentation to specific structures and objects identified by morphology processing. For example in a Cajal Bodies (CB) dynamics study (Platani M., Goldberg I., Lamond A., Swedlow S. “Cajal body dynamics and association with chromatin are ATP-dependent”. Nature Cell Biology. 2002 July; 4: 502-508), CBs identified in the target processing can be spatially related to the chromatin structures identified in the morphology processing. In semiconductor or electronic automatic defect classification or military automatic target classification applications, spatial reasoning relates the spatial relations among the components of defect arrangements or target structures to arrive at a classification decision.
In practical applications involving spatial decisions, it is highly desirable to have an automatic method to extract spatial reasoning features and generate spatial reasoning rules that could distinguish subtle differences and can compensate for measurement imperfection, noise, and uncertainty.
Prior art approaches use symbolic representations such as wire frame, surface-edge-vertex, generalized cylinder, superquadric, octree, etc. for spatial entity representations (Haralick, R M, Shapiro, R G, “Computer and Robot Vision”, Vol. II, PP440-453, Addison Wesley, 1993). Relational distance based matching is often used for spatial reasoning based on symbolic representations. This class of methods suffers from the non-numerical nature of the representation and data processing where it is difficult to handle uncertainty and noise from data and measurements. Furthermore, it is difficult to automatically generate spatial mapping features and automatically generate or discover spatial mapping rules corresponding to events or targets of interest. Therefore, spatial reasoning rules are often defined by human heuristics. Human defined rules are primitive, i.e. non-robust. They are incapable of distinguishing subtle differences; neither can they compensate for imperfect measurements.